#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    // 动态规划
    int maxTurbulenceSize(vector<int> &arr)
    {
        if (arr.size() == 1)
            return 1;
        // 状态表示dp[i]以i位置为结尾的最长湍流长度
        // 画图分析 状态转移方程
        vector<int> dp(arr.size(), 0);
        dp[0] = 1;
        dp[1] = arr[0] == arr[1] ? 0 : 2;
        for (int i = 2; i < arr.size(); i++)
        {
            if (arr[i] == arr[i - 1])
                dp[i] = 1;
            else
                dp[i] = ((arr[i - 2] > arr[i - 1]) ? arr[i] > arr[i - 1] : arr[i] < arr[i - 1]) ? dp[i - 1] + 1 : 2;
        }
        return *max_element(dp.begin(), dp.end());
    }
    // 滑动窗口
    int maxTurbulenceSize(vector<int> &arr)
    {
        if (arr.size() == 1)
            return 1;
        int l = 0, r = 1, ans = 1;
        bool lower = false;
        while (l + 1 < arr.size() && arr[l] == arr[l + 1])
            l++;
        r = l + 1;
        lower = !arr[l] > arr[r - 1];
        while (r < arr.size())
        {
            if (lower ? arr[r - 1] < arr[r] : arr[r - 1] > arr[r])
            {
                r++;
                lower = !lower;
            }
            else
            {
                ans = max(ans, r - l);
                l = r - 1;
                while (l + 1 < arr.size() && arr[l] == arr[l + 1])
                    l++;
                r = l + 2;
                lower = arr[l] > arr[l + 1];
            }
        }
        return max(ans, r - l);
    }
};